Countability of a Set
All sets can be classified as either countable or uncountable.
Countable Sets
A set \(S\) is countable if there exists an injection from it to the natural numbers, that is \(|S| \leq |\mathbb{N}|\).
If \(S\) is countably infinite, then \(|S| = |\mathbb{N}|\) and there is a bijection from \(S\) to \(\mathbb{N}\).
Such a bijection gives a natural way of listing the elements of \(S\), hence the name countable. Similarly, the ability to list the elements of \(S\) gives such a bijection.
This idea is demonstrated explicitly in the proof that rational numbers are countable.
Using the cardinality in terms of surjections result (with axiom of choice), we know that \(S\) is countable if there is a function \(f : \mathbb{N} \to S\) such that
Uncountable Sets
If a set is not countable, then it is uncountable.